package Offer;

/**
 * I. 斐波那契数列
 *
 * @author 是阿秋啊
 * @date 2022/04/06 21:16
 **/
public class Num10 {
    public int fib(int n) {
        // 方法一：动态规划
//        if (n <= 1) {
//            return n;
//        }
//        int a = 0;
//        int b = 1;
//        for (int i = 2; i < n; i++) {
//            int temp = a;
//            a = b;
//            b = (temp + b)%1000000007;
//        }
//        return b;
        // 方法二： 记忆递归法
        if (n <= 1) {
            return n;
        }
        int[] f = new int[n + 1];
        f[0] = 0;
        f[1] = 1;
        for (int i = 2; i < f.length; i++) {
            f[i] = -1;
        }
        int ret = helper(f, n);
        return ret;
    }

    private int helper(int[] f, int n) {
        if (f[n] != -1) {
            return f[n];
        }
        f[n] = (helper(f, n - 1) + helper(f, n - 2))%1000000007;
        return f[n];
    }
}
